Package edu.claflin.finder.algo

Class BronKerbosch

java.lang.Object
edu.claflin.finder.algo.Algorithm
edu.claflin.finder.algo.BronKerbosch
All Implemented Interfaces:
Processable<Graph,Graph>
public class BronKerbosch extends Algorithm
Bron-Kersboch Algorithm to find Maximal Cliques and Bicliques.
See Also:

  • Field Details

    • bipartite

      private boolean bipartite

  • Constructor Details

    • BronKerbosch

      public BronKerbosch(ArgumentsBundle bundle)
      Public constructor for initializing the Bron Kersbboch with default conditions.
      Parameters:
      bundle - the ArgumentsBundle containing the instantiation arguments.

  • Method Details

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • process

      public ArrayList<Graph> process(Graph graph)
      Processes data.
      Finds the Maximal Cliques of a Graph or the Maximal Biclique of a Bipartite Graph if the bipartite argument is set to true.
      Parameters:
      graph - the Graph object to search through.
      Returns:
      the ArrayList of Graph objects holding all found subgraphs.

    • maximalCliques

      private List<Graph> maximalCliques(Graph graph)
      Given a graph, finds all complete subgraphs, and then returns the largest one.
      Parameters:
      graph - the graph
      Returns:
      the largest complete subgraph (clique)

    • maximalBicliques

      private List<Graph> maximalBicliques(Graph graph)
      Gets the Maximal Complete Bipartite Graphs from the input Graph using Bron-Kersboch.
      Parameters:
      graph - the input Graph
      Returns:
      the Maximal Complete Bipartite Graphs

    • bronKerboschClique

      private List<Graph> bronKerboschClique(Graph graph)
      Given a graph, finds all complete subgraphs.
      Parameters:
      graph - the graph
      Returns:
      a List of complete subgraphs, unordered

    • bronKerboschBiclique

      private List<Graph> bronKerboschBiclique(Graph graph)
      Finds all bicliques within a bipartite graph. This is done by adding edges between every nodes in a partite set in both partite sets, using the above algorithm, and then removing all the added edges from the results. THIS ONLY WORKS ON GRAPHS THAT ARE BIPARTITE!
      Parameters:
      graph - the bipartite graph
      Returns:
      array list of bicliques

    • bronKerbosch

      private void bronKerbosch(List<List<Node>> results, List<Node> clique, List<Node> candidates, List<Node> excluded)
      Recursive helper method to do the above.
      Parameters:
      results - result list. Passed between recursive calls to create output
      clique - the current Clique being constructed; Graph r in Wikipedia link
      candidates - the candidate Nodes for the Clique; Graph p in Wikipedia link
      excluded - the Nodes to be excluded from the Clique; Graph x in Wikipedia link

    • addEdgesInParititeSet

      private void addEdgesInParititeSet(Graph graph, List<Node> list)
      Adds edges to a Graph between all Nodes in a partite set. Remove these edges later with removeEdgesInPartiteSet(edu.claflin.finder.logic.Graph,java.util.List<edu.claflin.finder.logic.Node>).
      Parameters:
      graph - the Graph to add the Edges to
      list - the partite set

    • removeEdgesInPartiteSet

      private void removeEdgesInPartiteSet(Graph graph, List<Node> list)
      Removes edges in a Graph between all Nodes in a partite set.
      Parameters:
      graph - the Graph to remove the Edges from
      list - the partite set

    • nameGraphs

      private List<Graph> nameGraphs(List<Graph> graphs, String originalName, boolean bipartite)